十二省联考2019 乱写

imily's notebook

2021-02-04

异或粽子

可持久化 Trie 树 + 「超级钢琴」做法。

加强版：$k \leq \frac{n(n - 1)}{2}$。题解

很自然套路的题，容易想到建边用图做，也就是一个 $A$ 向它支配的 $B$ 连边，这个 $B$ 再向以它为前缀的 $A$ 连边，暴力连 $O(n^2)$，考虑优化。

老套路，考虑图/树优化建边，这里对反串建 $SAM$，把 $A$ 串和 $B$ 串挂在对应的后缀树节点下，同个节点挂着的串相邻连边就避免了一个 $A$ 向一堆 $A$ 连的情况。

咕咕

这题不讲唔得，它用繁多的变量来搞你心态！~~大意了啊没有闪~~

撇开这点，题并不难（但有点考逻辑

首先发现派系和阵营是交错的，不管城市选什么阵营，里面的学校都可以任意选派系，城市的决定和学校的决定共同决定了导师。也就是说城市和学校独立。

先考虑 $k = 0$ 的情况，分别 $dp$ 算出 $f[i, j]$ 表示前 $i$ 个城市，$j$ 个人在蓝阵营的方案数；
$g[i, j]$ 表示前 $i$ 个城市，$j$ 个人在鸭派系的方案数。合法的相乘。

按照选课的套路，$k = 0$ 的情况，没有限制的城市和学校同上做；
$k \neq 0$，有限制的城市需要选同个阵营，同城市的学校就必须捆绑考虑了：$f[i, j, k]$ 表示前 $i$ 个城市蓝阵营人数为 $j$，鸭派系人数为 $k$ 的方案数。

然后滚掉一维就能 AC 辣!

撕烤怎么合并链，必然是贪心的大配大、小配小。拿堆维护一下，加个启发式合并就 AC 了。

别被高大上的题目唬住了！思路就是算一个救援队的答案，然后 $k$ 次方。点 $x$ 子树里和子树外的要分开算。考虑直接算会算重——一个连通块会被算多次，应用经典“点减边”思想——连通块中点数 = 边数 $+ 1$，就用点的答案减去边的答案。

$f[x, i]$ 表示子树里深度不超过 $i$ 的连通块方案数，$g[x, i]$ 表示不包括子树里（但包括 $x$）的深度不超过 $i$ 的连通块方案数，两个一乘岂不美哉？

转移方程超好写：

$n$ $1e6$, $dp$ 又与深度有关，于是想到长剖优化。本题的思路到此为止，接下来都是细节

$f$ 可以直接算，但是 $g$ 里面那个 $\prod$ 不好搞。

用回退栈可以维护，做 $f$ 的时候从长到短遍历子树，做 $g$ 的时候从短到长遍历子树。